// https://leetcode.cn/problems/russian-doll-envelopes/description/

// 算法思路总结：
// 1. 排序+LIS解决俄罗斯套娃信封问题
// 2. 按宽度升序、高度降序排序避免同宽度多选
// 3. 在高度序列中寻找最长递增子序列
// 4. 使用贪心+二分优化LIS计算过程
// 5. 时间复杂度：O(n log n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) 
    {
        int m = envelopes.size();

        sort(envelopes.begin(), envelopes.end(), [&](const vector<int>& v1, const vector<int>& v2){
            return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
        });

        vector<int> ret;
        for (int i = 0 ; i < m ; i++)
        {
            if (ret.empty() == true || envelopes[i][1] > ret.back())
            {
                ret.push_back(envelopes[i][1]);
            }
            else 
            {
                auto it = lower_bound(ret.begin(), ret.end(), envelopes[i][1]);
                *it = envelopes[i][1];
            }
        }

        return ret.size();
    }
};

int main()
{
    vector<vector<int>> envelopes1 = {{5,4},{6,4},{6,7},{2,3}};
    vector<vector<int>> envelopes2 = {{1,1},{1,1},{1,1}};

    Solution sol;

    cout << sol.maxEnvelopes(envelopes1) << endl;
    cout << sol.maxEnvelopes(envelopes2) << endl;

    return 0;
}